/**
 * @version Create on 2012-11-2
 * @author Yinzi Chen
 */

public class ImplementStrStr {

	public int[] buildNext(String needle) {
		int m = needle.length();
		int[] next = new int[m];
		next[0] = -1;
		int i = -1, j = 1;
		while (j < m) {
			if (i < 0 || needle.charAt(i) == needle.charAt(j - 1)) {
				next[j++] = ++i;
			} else {
				i = next[i];
			}
		}
		return next;
	}

	public String strStr(String haystack, String needle) {
		int n = haystack.length(), m = needle.length();
		if (m == 0)
			return haystack;
		else if (n < m)
			return null;
		int[] next = buildNext(needle);
		int i = 0, j = 0;
		while (i < n && j < m) {
			if (n - i < m - j)
				return null;
			if (j < 0 || haystack.charAt(i) == needle.charAt(j)) {
				i++;
				j++;
			} else {
				j = next[j];
			}
		}
		return haystack.substring(i - m);
	}

	public static void main(String[] args) {
		ImplementStrStr a = new ImplementStrStr();
		System.out.println(a.strStr("missi", "ssi"));
		int next[] = a.buildNext("aaaaaaa");
		for (int i = 0; i < next.length; ++i) {
			System.out.print(next[i] + " ");
		}
		System.out.println();
		a.strStr("aaaeeaaaaeeeeeeeeeeeeeeee", "aaaa");
		// for (int i = 0; i < next.length; ++i) {
		// System.out.print(next[i] + " ");
		// }
		// System.out.println();
	}

}
